/**
 * https://leetcode.cn/problems/count-different-palindromic-subsequences/submissions/582007565/
 * 730.统计不同回文子序列
 * difficulty 陈贝纯 11.21
 * 区间dp
 */

class Solution {
public:
    const int M=1e9+7;
    int countPalindromicSubsequences(string s) {
        int n=s.size();
        vector<vector<long long>> dp(n,vector<long long>(n,0));
        for(int i=0;i<n;++i)
        dp[i][i]=1;
        for(int i=n-1;i>=0;--i){
            for(int j=i+1;j<n;++j){
                if(s[i]==s[j]){
                    int l=i+1;
                    int r=j-1;
                    while(s[l]!=s[i]&&l<j) l++;
                    while(s[r]!=s[i]&&r>i) r--;
                    if(l>r) dp[i][j]=dp[i+1][j-1]*2+2;
                    else if(l==r) dp[i][j]=dp[i+1][j-1]*2+1;
                    else dp[i][j]=dp[i+1][j-1]*2-dp[l+1][r-1]+M;
                }else
                    dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+M;
                dp[i][j]%=M;
            }
        }
        return dp[0][n-1];
    }
};